package com.dataStructure.greedy;

import java.util.*;

public class LeetCode {

    public static void main(String[] args) {
        List<Integer> integers = partitionLabels("ababcbacadefegdehijhklij");
        System.out.println(integers.toString());
    }




    /**
     *  集合覆盖问题
     *  https://x7xrycxzti.feishu.cn/file/boxcnwNAMrX74inV7wl6SQ8FCod
     */
    public Set<String> cover() {
        Map<String, Set<String>> map = new HashMap<>();

        HashSet<String> result = new HashSet<>();

        HashSet<String> target = new HashSet<>();
        target.add("HuNan");


        while(target.size() != 0) {
            int maxCity = 0;
            String bordCadKey = "";
            for (String key : map.keySet()) {
                Set<String> eSet = map.get(key);
                Set<String> jiaojiSet = jiaoji(eSet, target);
                if (jiaojiSet.size() > maxCity) {
                    maxCity = jiaojiSet.size();
                    bordCadKey = key;
                }
            }
            map.remove(bordCadKey);
            result.add(bordCadKey);
            target.removeAll(map.get(bordCadKey));

        }

        return result;

    }

    public Set<String> jiaoji(Set<String> a, Set<String> b) {
        HashSet<String> res = new HashSet<>();

        res.addAll(a);
        res.retainAll(b);
        return  res;
    }



    public int eraseOverlapIntervals2(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[1] != o2[1]) {
                return o1[1] - o2[1];
            }
            else {
                return  o1[0] - o2[0];
            }
        });

        for (int[] interval : intervals) {
            System.out.println(Arrays.toString(interval));
        }

        int ct = 0;
        int jieshu = Integer.MIN_VALUE;
        for (int i = 0; i < intervals.length; i++) {
            int[] interval = intervals[i];

            if (jieshu <= interval[0]) {
                ct++;
                jieshu = interval[1];
            } else {
                continue;
            }

        }

        return intervals.length - ct;

    }

    public static List<Integer> partitionLabels(String s) {
        LinkedList<Integer> list = new LinkedList<>();
        if (s.length() ==0) {
            return list;
        }
        HashMap<Character, Integer> map = new HashMap<>();

        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            map.put(c,i);
        }
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < chars.length; i++) {

            char c = chars[i];
            Integer cur = map.get(c);

            if (cur >= max) {
                max = cur;
            }
            if (i >= max) {
                int sum = 0;
                for (Integer ct : list) {
                    sum += ct;
                }
                list.add(i + 1 - sum);
            }

        }


        return list;

    }
    /**
     * 435 ,无重叠区间
     */
    public static int eraseOverlapIntervals1(int[][] intervals) {
        Arrays.sort(intervals, ((o1, o2) -> {
            if (o1[0] > o2[0]) {
                return 1;
            }
            else if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            else
                return -1;
        }));

        LinkedList<int[]> list = new LinkedList<>();

        for (int i = 0; i < intervals.length; i++) {
            int[] interval = intervals[i];

            if (list.size() == 0) {
                list.add(interval);

            }
            else {
                int[] last = list.peekLast();
                if (last[1] > interval[0] && last[1] < interval[1]) {
                    continue;
                }
                else{
                    list.add(interval);
                }
            }
        }
        return intervals.length - list.size();
    }






    /**
     * 56，合并区间
     * @param intervals
     * @return
     */
    public int[][] eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] > o2[0]) {
                    return 1;
                }
                else if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                else
                    return -1;

            }
        });

        LinkedList<int[]> list = new LinkedList<>();

        for (int i = 0; i < intervals.length; i++) {
            int[] interval = intervals[i];
            if (list.size() == 0) {
                list.add(interval);
            }
            else {
                int[] last = list.peekLast();
                if (last[1] >= interval[0] && last[1] <= interval[1]) {
                    last[1] = interval[1];
                }

                if (last[1] < interval[1] ) {
                    list.add(interval);
                }
            }

        }

        return list.toArray(new int[0][0]);
    }


    /**
     * 56. 合并区间

     */

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1) {
            return intervals;
        }

        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] > o2[0]) {
                return 1;
            }
            else if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            else
                return -1;

        });

        LinkedList<int[]> list = new LinkedList<>();

        for (int i = 1; i < intervals.length - 1; ) {
            int[] interval = intervals[i];
            //大于第一个，小于第二个

            //大于第一个和第二个


        }

        return list.toArray(new int[list.size()][]);


    }


    /**
     * 406. 根据身高重建队列
     */
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2) -> {
            if (o1[0] > o2[0]) {
                return -1;
            }
            else if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            else
                return 1;
        });
        LinkedList<int[]> list = new LinkedList<>();
        for (int i = 0; i < people.length; i++) {
            int[] person = people[i];
            list.add(person[0],people[i]);

        }
        return list.toArray(new int[people.length][]);
    }


    /**
     * 860. 柠檬水找零
     */
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0, twenty = 0;

        for (int i = 0; i < bills.length; i++) {
            int bill = bills[i];

            if (bill == 5) {
                five ++;
            }
            if (bill == 10) {
                if (five < 1) {
                    return false;
                }
                five--;
                ten++;
            }

            if (bill == 20) {
                //没有10元
                if (ten < 1) {
                    if(five < 3) {
                        return false;
                    } else {
                        five -= 3;
                        twenty++;
                    }
                }
                //有10元钞票
                else {
                    if (five < 1) {
                        return false;
                    } else {
                        ten--;
                        five--;
                        twenty++;
                    }
                }
            }
        }
        return true;
    }


    /**
     * 135 ，分发糖果
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
//        int[] result = new int[ratings.length];
//
//        Arrays.fill(result,1);
//        for (int i = 1; i < result.length; i++) {
//            if (ratings[i] > ratings[i - 1]) {
//                result[i] = result[i - 1]  + 1;
//            }
//        }
//
//        for (int i = result.length -2 ; i >=0; i--) {
//            if (ratings[i] > ratings[i + 1]) {
//                result[i] = Integer.max(result[i + 1] + 1,result[i]);
//            }
//        }
//        c

        int[] result = new int[ratings.length];

        Arrays.fill(result,1);
        for (int i = 1; i < result.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                result[i] = result[i - 1]  + 1;

            }
            else if (ratings[i] < ratings[i - 1]) {
                result[i - 1] = result[i] + 1;
            }

        }
        return Arrays.stream(result).sum();

    }

    /**
     * 134 .加油站
     *
     * 贪心算法，从两次考虑
     */
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int total = 0;
        int rest = 0;
        int index = 0;
        for (int i = 0 ; i < gas.length; i++) {
            total += gas[i] - cost[i];
            rest += gas[i] - cost[i];
            if (rest < 0) {
                index  = i +1;
                rest = 0;
            }
        }
        if (total < 0) {
            return -1;
        }else  {
            return index;
        }
    }


    /**
     * 134 .加油站
     *
     * 此方法，暴力已经超时
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length ; i++) {
            int sy = 0;
            for (int j = i; j < i + gas.length; j++) {
                //没有出环的情况
                if (j < gas.length) {
                    sy += gas[j];
                    if (sy < cost[j]) {
                        break;
                    }
                    else {
                        sy -= cost[j];
                        if (j == i + gas.length - 1) {
                            return i;
                        }
                    }
                }
                //出环的情况
                else {
                    sy +=  gas[j - gas.length];
                    if (sy < cost[j - gas.length]) {
                        break;
                    }
                    else {
                        sy -= cost[j - gas.length];
                        if (j == i + gas.length - 1) {
                            return i;
                        }
                    }
                }
            }
        }
        return -1;
    }
    /**
     * 1005. K 次取反后最大化的数组和
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
            int index = 0;
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] < min) {
                    index = j;
                    min = nums[j];
                }
            }
            nums[index] = -nums[index];
        }

        int sum = Arrays.stream(nums).sum();
        return sum;
    }

    /**
     * 去数组的最小值
     *
     */
    public int minAr(int[] ar){
        int min = Integer.MAX_VALUE;
        for (int e : ar) {
            min = Integer.min(e,min);
        }

        return min;
    }

    /**
     * 45 跳跃游戏 2
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
       if(nums.length == 1) {
           return 0;
       }
       int range = 0;
       int ct = 0;
       int cur = 0;
       for (int i =0 ; i <= range ; i++) {
           range = Integer.max(range, i + nums[i]);
           if (range >= nums.length - 1) {
               ct++;
               return ct;
           }
           if (cur == i) {
               cur = range;
               ct++;
           }

       }
       return ct;
    }

    /**
     * 55 跳跃游戏
     */
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }

        int range = 0;
        for (int i = 0; i <= range ; i++) {
            range = Integer.max(range, i + nums[i]);
            if (range == nums.length - 1) {
                return true;
            }
        }

        return false;
    }


    /**
     * 力扣 455 分发饼干
     *
     */
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int sum = 0;
        for (int i = 0,j=0;i < s.length && j < g.length;i++) {
            if (s[i] >= g[j]) {
                sum++;
                j++;
            }
        }
        return sum;
    }
}
